#include <stdio.h>
#include <stdlib.h>

// 修改结点结构：增加线索标志位
typedef struct BiTNode
{
    int data;               // 数据域
    struct BiTNode *lchild; // 左孩子指针
    struct BiTNode *rchild; // 右孩子指针
    int ltag;               // 左线索标志：0=孩子指针, 1=前驱线索
    int rtag;               // 右线索标志：0=孩子指针, 1=后继线索
} BiTNode, *BiTree;

// 初始化树
void InitTree(BiTree *T)
{
    *T = NULL; // 树根指针置空
}

// 插入结点（初始化线索标志为0）
bool InsertNode(BiTree *T, int value, BiTree parent, int isLeft)
{
    BiTNode *newNode = (BiTNode *)malloc(sizeof(BiTNode));
    if (!newNode)
        return false;

    newNode->data = value;
    newNode->lchild = NULL;
    newNode->rchild = NULL;
    newNode->ltag = 0; // 初始化为孩子指针
    newNode->rtag = 0; // 初始化为孩子指针

    if (parent == NULL)
    {
        if (*T != NULL)
        {
            free(newNode);
            return false;
        }
        *T = newNode;
        return true;
    }

    if (isLeft)
    {
        if (parent->lchild != NULL)
        {
            free(newNode);
            return false;
        }
        parent->lchild = newNode;
    }
    else
    {
        if (parent->rchild != NULL)
        {
            free(newNode);
            return false;
        }
        parent->rchild = newNode;
    }
    return true;
}

// 使用递归代替栈实现中序遍历
void InOrderThreading(BiTree T, BiTree *pre)
{
    if (T == NULL)
        return;

    // 线索化左子树
    InOrderThreading(T->lchild, pre);

    // 处理当前结点的前驱线索
    if (T->lchild == NULL)
    {
        T->lchild = *pre;
        T->ltag = 1;
    }

    // 处理前驱结点的后继线索
    if (*pre != NULL && (*pre)->rchild == NULL)
    {
        (*pre)->rchild = T;
        (*pre)->rtag = 1;
    }

    // 更新前驱
    *pre = T;

    // 线索化右子树
    InOrderThreading(T->rchild, pre);
}

// 中序线索遍历（利用线索直接遍历）
void ThreadedInOrder(BiTree T)
{
    if (T == NULL)
    {
        printf("Empty tree\n");
        return;
    }

    // 找到中序遍历起点（最左结点）
    BiTree current = T;
    while (current->lchild != NULL && !current->ltag)
    {
        current = current->lchild;
    }

    // 利用线索遍历
    printf("Threaded Inorder Traversal: ");
    while (current != NULL)
    {
        printf("%d ", current->data);

        // 如果存在后继线索直接跳转
        if (current->rtag)
        {
            current = current->rchild;
        }
        // 否则进入右子树的最左结点
        else
        {
            current = current->rchild;
            if (current != NULL)
            {
                while (current->lchild != NULL && !current->ltag)
                {
                    current = current->lchild;
                }
            }
        }
    }
    printf("\n");
}

// 释放线索树的内存
void DestroyTree(BiTree T)
{
    if (T == NULL)
        return;

    // 如果左指针是孩子指针，递归释放左子树
    if (!T->ltag)
        DestroyTree(T->lchild);

    // 如果右指针是孩子指针，递归释放右子树
    if (!T->rtag)
        DestroyTree(T->rchild);

    free(T);
}

int main()
{
    BiTree T;
    InitTree(&T);

    // 构建测试树
    InsertNode(&T, 1, NULL, 1);      // 根结点
    InsertNode(&T, 2, T, 1);         // 1的左孩子
    InsertNode(&T, 3, T, 0);         // 1的右孩子
    InsertNode(&T, 4, T->lchild, 1); // 2的左孩子
    InsertNode(&T, 5, T->lchild, 0); // 2的右孩子
    InsertNode(&T, 6, T->rchild, 0); // 3的右孩子

    // 执行线索化
    BiTree pre = NULL;
    InOrderThreading(T, &pre);

    // 设置最后一个结点的后继为NULL
    if (pre != NULL)
    {
        pre->rchild = NULL;
        pre->rtag = 1;
    }

    // 线索化遍历测试
    ThreadedInOrder(T);

    // 释放内存
    DestroyTree(T);

    return 0;
}